/*
 * @lc app=leetcode.cn id=2104 lang=cpp
 *
 * [2104] 子数组范围和
 */

// @lc code=start
class Solution
{
public:
    long long getValue(const deque<int> &q_min, const deque<int> &q_max, vector<int> &nums)
    {
        // 迭代器
        auto p = q_min.begin(), q = q_max.begin();
        int pre_pos = -1;
        long long res = 0;
        while (p != q_min.end())
        {
            // 取出最小值
            int pos = min(*p, *q);
            // 计算和
            res += (long long)(pos - pre_pos) * (long long)(nums[*q] - nums[*p]);
            // 如果最小值是当前值，则迭代器后移
            if (*p == pos)
                p++;
            // 如果最大值是当前值，则迭代器后移
            if (*q == pos)
                q++;
            // 更新最小值
            pre_pos = pos;
        }

        return res;
    }
    long long subArrayRanges(vector<int> &nums)
    {
        deque<int> q_min, q_max;
        long long ans = 0;
        int n = nums.size();

        for (int i = 0; i < n; i++)
        {
            while (!q_min.empty() && nums[i] <= nums[q_min.back()])
            {
                q_min.pop_back();
            }
            while (!q_max.empty() && nums[i] >= nums[q_max.back()])
            {
                q_max.pop_back();
            }
            q_min.push_back(i), q_max.push_back(i);
            ans += getValue(q_min, q_max, nums);
        }

        return ans;
    }
};
// @lc code=end
